package _17_graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: mornd
 * @dateTime: 2023/6/26 - 10:56
 * 最小生成数-Prim算法
 */
public class Prim {
    @Test
    public void test() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        Vertex v7 = new Vertex("v7");

        // 参照 img/最小生成树.png
        v1.edges = List.of(new Edge(v2, 2), new Edge(v4, 1), new Edge(v3, 4));
        v2.edges = List.of(new Edge(v1, 2), new Edge(v4, 3), new Edge(v5, 10));
        v3.edges = List.of(new Edge(v1, 4), new Edge(v4, 2), new Edge(v6, 5));
        v4.edges = List.of(new Edge(v1, 1), new Edge(v2, 3), new Edge(v5, 7),
                new Edge(v7, 4), new Edge(v6, 8), new Edge(v3, 2));
        v5.edges = List.of(new Edge(v2, 10), new Edge(v4, 7), new Edge(v7, 6));
        v6.edges = List.of(new Edge(v3, 5), new Edge(v4, 8), new Edge(v7, 1));
        v7.edges = List.of(new Edge(v4, 4), new Edge(v5, 6), new Edge(v6, 1));

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
        prim(v1, graph);
    }

    private void prim(Vertex source, List<Vertex> graph) {
        List<Vertex> list = new ArrayList<>(graph);
        source.dist = 0;

        while (!list.isEmpty()) {
            Vertex curr = chooseMinDistVertex(list);
            updateNeighborsDist(curr, list);
            list.remove(curr);
        }

        for (Vertex vertex : graph) {
            System.out.println("name=" + vertex.name + ",dist=" + vertex.dist
                    + ",prev=" + (vertex.prev != null ? vertex.prev.name : null));
        }
    }

    private void updateNeighborsDist(Vertex curr, List<Vertex> list) {
        for (Edge edge : curr.edges) {
            Vertex neighbor = edge.linked;
            // contains=false，表示该顶点已经访问过了，并且它的dist已更新为最短的了，无需再调整了
            if (list.contains(neighbor)) {
                // 这里区别于 dijkstra 算法
//                int newDist = curr.dist + edge.weight;
                int newDist = edge.weight;
                if (newDist < neighbor.dist) {
                    neighbor.dist = newDist;
                    neighbor.prev = curr;
                }
            }
        }
    }

    /**
     * 从集合中查找距离最小的顶点返回
     *
     * @param list
     * @return
     */
    private Vertex chooseMinDistVertex(List<Vertex> list) {
        Vertex min = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i).dist < min.dist) {
                min = list.get(i);
            }
        }
        return min;
    }
}
